package PrefixSum;

import java.util.HashMap;

//https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
public class l_974 {
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length, sum = 0, ans = 0;
        HashMap<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1); //当sum为k的倍数时会用到
        for(int i = 0; i < n; i++)
        {
            sum += nums[i];
            int x = (sum % k + k ) % k; //java负数%正数会变成负数, 这样可以修正
            ans += hash.getOrDefault(x, 0); //这里利用了同余定理
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }
        return ans;
    }
}
